/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class OutofBoundaryPaths {
	long result=0;
	int limit=1000000007;
	int[][] dirs={{-1,0},{1,0},{0,1},{0,-1}};

    public int findPaths(int m, int n, int N, int i, int j) {
    	int[][] dp1=new int[m][n];//上一步的结果
    	int[][] dp2=new int[m][n];
    	int result=0;
    	dp1[i][j]=1;
    	for (int k = 0; k < N; k++) {
			for (int p = 0; p < m; p++) {
				for (int q = 0; q < n; q++) {
					if(dp1[p][q]==0)
						continue;
					for (int[] dir : dirs) {
						int x=p+dir[0];
						int y=q+dir[1];
						if(x<0||x==m||y<0||y==n){
							result+=dp1[p][q];
							result%=limit;
						}else {
							dp2[x][y]+=dp1[p][q];
							dp2[x][y]%=limit;
						}
					}
				}
			}
			dp1=dp2;
			dp2=new int[m][n];
		}
    	return result;
    }
    //递归实现，超时了
//	/**
//	 * 
//	 * @param m 总共方格数
//	 * @param n
//	 * @param N 限制的步数
//	 * @param i 起始位置坐标
//	 * @param j
//	 * @return
//	 */
//    public int findPaths(int m, int n, int N, int i, int j) {
//    	geneMyPath(m, n, N, i, j);
//    	return (int) result;
//    }
//    public void geneMyPath(int m,int n,int N,int i,int j) {
//		if(i==-1||i==m||j==-1||j==n){
//			result++;
//			if(result==limit){
//				result-=limit;
//			}
//			return;
//		}
//		if(N==0){
//			return;
//		}
//		geneMyPath(m, n, N-1, i-1, j);//向左
//		geneMyPath(m, n, N-1, i+1, j);//向左
//		geneMyPath(m, n, N-1, i, j-1);//向左
//		geneMyPath(m, n, N-1, i, j+1);//向左
//	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		OutofBoundaryPaths outofBoundaryPaths=new OutofBoundaryPaths();
		int m = 1, n = 3, N = 3, i = 0, j = 1;
		System.out.println(outofBoundaryPaths.findPaths(m, n, N, i, j));
	}

}
